/*
 * @lc app=leetcode.cn id=221 lang=typescript
 *
 * [221] 最大正方形
 */

// @lc code=start

//  思路：动态规划
//  dp[i][j] 表示以(i,j)为右下角的正方形的边长的最大值
//  1. matrix[i][j] = 0
//  dp[i][j] = 0
//  2. matrix[i][j] = 1
//  dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

//  复杂度：O(mn) O(mn)

function maximalSquare(matrix: string[][]): number {
    const x = matrix.length, y = matrix[0].length
    const dp = Array.from(new Array(x), () => new Array(y).fill(0))
    let res = 0
    // 赋初始值，首行首列
    for (let j = 0; j < y; j++) {
        dp[0][j] = parseInt(matrix[0][j])
        res = Math.max(res, dp[0][j])
    }
    for (let i = 0; i < x; i++) {
        dp[i][0] = parseInt(matrix[i][0])
        res = Math.max(res, dp[i][0])
    }

    for (let i = 1; i < x; i++) {
        for (let j = 1; j < y; j++) {
            dp[i][j] = matrix[i][j] === '0' ? 0 : Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
            res = Math.max(res, dp[i][j])
        }
    }

    return res * res
};
// @lc code=end


console.log(maximalSquare([["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]));
